package com.linwen.excise.huaweiOJ;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wlw
 * @date 2023/3/22 11:03 PM
 */
public class _三分之一链表结点 {
    public static void main(String[] args) {
        Node root = new Node();
        Node temp = root;
        // 构建一个链表
        for (int i = 0; i < 9; i++) {
            Node node = new Node();
            node.key = i+1;
            temp.next = node;
            temp = node;
        }
        System.out.println(function(root));
        System.out.println(function2(root));


    }

    private static int function2(Node root) {
        Map<Integer,Node> map = new HashMap<Integer,Node>();
        int index = 0;
        while (root!=null){
            map.put(index++,root);
            root = root.next;
        }
        return map.get(index/3).key;
    }

    private static int function(Node root) {
        Node fast = root;
        Node slow = root;
        int count = 0;
        while (true){
            if(fast.next!=null){
                fast = fast.next;
                count++;
                if(count==3){
                    slow = slow.next;
                    count = 0;
                }
            }else{
                break;
            }
        }
        return slow.key;

    }

    static class Node{
        int key;
        Node next;
        Node(){}
        Node(int k,Node next){
            this.key = k;
            this.next = next;
        }
    }
}
